Ví dụ Định_lý_luồng_cực_đại_lát_cắt_cực_tiểu

Một mạng với luồng cực đại và ba lát cắt cực tiểu

Hình bên phải là một mạng với các nút V = { s , o , p , q , r , t } {\displaystyle V=\{s,o,p,q,r,t\}} , và luồng cực đại là một luồng tổng từ nút phát s {\displaystyle s} tới nút thu t {\displaystyle t} có giá trị bằng 5. (Đây thực ra là luồng cực đại duy nhất ta có thể tìm thấy trong mạng này.)

Có ba lát cắt cực tiểu trong mạng. Đối với lát cắt S = { s , p } , T = { o , q , r , t } {\displaystyle S=\{s,p\},T=\{o,q,r,t\}} , khả năng thông qua lát cắt là c ( s , o ) + c ( p , r ) = 3 + 2 = 5 {\displaystyle c(s,o)+c(p,r)=3+2=5} . Với S = { s , o , p } , T = { q , r , t } {\displaystyle S=\{s,o,p\},T=\{q,r,t\}} nó là c ( o , q ) + c ( p , r ) = 3 + 2 = 5 {\displaystyle c(o,q)+c(p,r)=3+2=5} . Và với S = { s , o , p , q , r } , T = { t } {\displaystyle S=\{s,o,p,q,r\},T=\{t\}} là c ( q , t ) + c ( r , t ) = 2 + 3 = 5 {\displaystyle c(q,t)+c(r,t)=2+3=5} .

Lưu ý rằng S = { s , o , p , r } , T = { q , t } {\displaystyle S=\{s,o,p,r\},T=\{q,t\}} không phải là một lát cắt cực tiểu, tuy trong luồng đã cho cả ( o , q ) {\displaystyle (o,q)} và ( r , t ) {\displaystyle (r,t)} đều đầy. Đó là do trong mạng còn dư G f {\displaystyle G_{f}} có một cung (r,q) với khả năng thông qua c f ( r , q ) = c ( r , q ) − f ( r , q ) = 0 − ( − 1 ) = 1 {\displaystyle c_{f}(r,q)=c(r,q)-f(r,q)=0-(-1)=1} .

Liên quan

Tài liệu tham khảo

WikiPedia: Định_lý_luồng_cực_đại_lát_cắt_cực_tiểu http://www.cs.yorku.ca/~aaw/Wang/MaxFlowStart.htm http://www2.toki.or.id/book/AlgDesignManual/BOOK/B... http://vnoi.info/vn/bai_viet/thuat_toan/luong_cuc_... http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/ma... http://laptrinh.sourceforge.net/hoctap/maxflow/ https://web.archive.org/web/20060516105136/http://... https://web.archive.org/web/20080111234829/http://... https://web.archive.org/web/20080212103425/http://... https://web.archive.org/web/20080507085718/http://...